package 面试;

import java.util.HashMap;
import java.util.Map;

/**
 * @author https://blog.csdn.net/tingting256/article/details/52550188
 * @author https://blog.csdn.net/nicolasyan/article/details/50840947
 */
public class BitCalculate {
    public static void main(String args[]) {
//        int a = 20;
//        int b = 5;
//        System.out.println(myAdd(a, b));
//        System.out.println(mySub(a, -b));//20-5会溢出得到错误结果
//        System.out.println(myMuti(a, b));
//        System.out.println(myDiv(a, b));
//        System.out.println(myDiv(a, -b));

        System.out.println(divide(10, 2));
    }

    public static int myAdd(int a, int b) {
        int sum;
        int carry;
        do {
            sum = a ^ b;
            carry = (a & b) << 1;//进位需要左移一位
            a = sum;
            b = carry;
        } while (carry != 0);
        return sum;
    }

    public static int mySub(int a, int b) {
        return myAdd(a, myAdd(~b, 1));
    }

    public static long myMuti(int a, int b) {
        boolean flag = (b < 0);
        if (flag) b = -b;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < 32; i++) {
            map.put(1 << i, i);
        }
        int sum = 0;
        while (b > 0) {
            int last = b & (~b + 1); //取得最后一个1
            int count = map.get(last);//取得相关的移位
            sum += a << count;
            b = b & (b - 1);
        }
        if (flag) sum = -sum;
        return sum;
    }

    public static int myDiv(int a, int b) {
        boolean flag = (a < 0) ^ (b < 0);
        if (a < 0)
            a = -a;
        if (b < 0)
            b = -b;
        if (a < b)
            return 0;
        int msb = 0;
        while ((b << msb) < a) {
            msb++;
        }
        int q = 0;
        for (int i = msb; i >= 0; i--) {
            if ((b << i) > a)
                continue;
            q |= (1 << i);
            a -= (b << i);
        }
        if (flag)
            return -q;
        return q;
    }

    public static int divide(int dividend, int divisor) {
        // 处理异常
        if (divisor == 0)
            return 0;
        int max = Integer.MAX_VALUE;
        int min = Integer.MIN_VALUE;
        // 处理最大最小值取模的情况。
        long divid = (long) dividend;
        long divi = (long) divisor;
        // 减少重复运算
        if (divi == 1)
            return (int) divid;
        if (divi == -1) {
            // 处理溢出
            if (divid <= min)
                return max;
            return (int) -divid;
        }
        // 默认除数为负数，下面会对除数的正负再判断的
        boolean flag = true;
        // 处理符号，将负数变成正数求结果，最后根据flag对结果区负数即可
        if (divid < 0) {
            divid = -divid;
            if (divi < 0) {
                divi = -divi;
            } else {
                // 除数不为负数，修改 flag
                flag = false;
            }
        } else if (divi < 0) {
            divi = -divi;
            flag = false;
        }
        long res = 0;
        long tmp = 0;
        long cnt = 1;
        // 左移一位相当于乘以2,右移一位相当于除以2.
        while (divi <= divid) {
            // 2^n次方
            cnt = 1;
            tmp = divi;
            // 找到第一个大于被除数的 2^n次方
            while (tmp <= divid) {
                //
                tmp <<= 1;
                cnt <<= 1; //
            }
            res += (cnt >> 1);
            // 减去基数的前一个数
            divid -= (tmp >> 1);
        }

        return flag ? (int) res : (int) -res;

    }
}